系统设计笔记，自用。
系统设计的大致流程
系统设计的流程可以大致分为以下的步骤：
1. 需求分类
由于在面试时我们只有30-40分钟的时间，所以知道准确的需求是必要的。比如设计一个类推特软件，我们要知道：
- 用户要推送推文或关注其他用户吗？
- 我们是否需要用户时间线功能？
- 推文是否有图片或视频？
- 只制作后端还是前后端同时？
- 需要搜索功能吗？
- 需要热搜榜吗？
- 是否需要对重要推文进行推送？
2. 系统接口定义
通过定义API,我们能够知道系统需要包含什么，同时能够确认是否搞错了需求。我们设计一个类推特软件时，接口会像这样：
- postTweet(user_id, tweet_data, tweet_location, user_location, timestamp,…)
- generateTimeline(user_id, current_time, user_location…)
- markTweetFavourite(user_id, tweet_id, timestamp…)
3. 规模估算
在设计系统前了解问题的规模是非常有帮助的，能帮助我们了解系统规模，系统划分，负载均衡和缓存策略。
- 系统的期望规模（推文篇数，推文的阅读数，我们每秒需要设计多少时间轴等）
- 储存空间的大小是多少？（当我们允许用户发送带图片的推文时，需要的存储空间是不同的）
- 带宽是多少？（这能帮我们决定我们怎样管理服务器网络和负载均衡。）
4. 定义数据模型
定义数据模型能让我们知道系统中数据是怎么流动的。这能帮我们划分和管理数据。在定义数据模型时，最好我们能够通过数据模型了解到系统中有多少实体（表名的划分），知道数据如何交互（外键，多对多对应表），还有不同的数据管理策略如储存，传输，加密（密码）等。如果实现一个类推特我们可以这样设计：
- User: UserID, Name, Email, DoB, CreationData, LastLogin, etc
- Tweet: TweetID, Content, TweetLocation, NumberOfLikes, TimeStamp, etc
- UserFollow: UserID1, UserID2
- FavouriteTweets: UserID, TweetID, TimeStamp
设计时我们就要考虑：我们用什么数据库系统？用MySQL固然是传统的选择，但是noSQL是否更好（noSQL在多对多上查询很方便，mysql需要查多张表）？我们是否需要固定的空间存储照片和视频？
5. 高级设计
现在我们应该画一个框图来确定我们需要实现哪些功能模块。
比如对于推特来说，我们需要多个程序/服务器来满足读写请求，同时在信息流前设置负载均衡。如果我们认为读请求相对写请求比较多的话，我们就应该让不同的服务器来分别处理读写请求（mysql读写分离）。在后端，我们需要一个高效的数据库来储存所有推文，同时支持大量写请求。我们还需要一个分布式的文件系统来保存照片和视频。
6. 细节设计
在与面试官的交流中，我们会知道他希望我们能够更加深入讨论哪些部分。此时，我们应当能够展示不同的架构，他们的优点缺点，以及为什么我们选择其中一个而不是另一个。系统设计没有固定答案，不同的条件下，我们要做出不同的选择。
- 在大量数据下，我们是否需要进行分库分表？我们需要将所有数据保存在同一个数据库吗？这会导致什么问题？
- 我们要怎么处理大量发帖或大量关注的用户？（多对多需要维护一张过渡表，该表只有两列，但行数很多）
- 想象一下翻阅朋友圈的场景，我们通常翻阅的总是最新的推文，所以不难想到用户请求的推文大部分是最新的（或者相关的）推文，我们是否应该对数据进行优化来加快读取最新推文的速度？
- 我们应该使用多少缓存，在哪里使用缓存来加速浏览？
- 哪个部分需要更多负载均衡？
7. 找到并解决系统的性能瓶颈
- 这个系统存在单点失效吗？（这个服务器宕机整个服务失效）我们要怎么避免单点失效？
- 我们是否有足够用户数据备份，使得即便一部分服务器失效，我们依然能够提供服务？
- 相似的，我们是否有足够的服务备份，在一部分服务失效时，仍能用备份服务顶上？
- 我们要怎么监控服务的性能？能否获得预警？能否在系统关键模块出错或效率降低时得到警告？
总结
总而言之，提前准备与良好的行动框架，是系统设计面试的关键。不论处理什么系统设计问题，都应当遵循这个流程。
设计一个短链接服务
我们为什么需要短链接服务？
将形如
https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/
转为
这能够帮助我们避免字数限制（微博），隐藏来源网站（网站链接分享限制），特定页面统计（短链接提供的功能）。
系统需求和目标
功能需求
- 对于给定的URL,我们的服务应该能够返回一个更短的链接，同时这个链接有它独一无二的标识。（通常格式是第三方网站地址/压缩后标识）
- 当用户访问我们提供的短链接，我们需要将其重定向原本的网址
- 用户应当能够选择定制独特的短链接
- 在一定时间后，短链接应该会过期。用户应当能够自主选择合适的过期时间
非功能需求
- 这个系统应当是高可用的，否则如果无门无法提供服务，所有的URL重定向都会失效
- URL重定向应当尽可能实时，以最小的延迟实现。
- 短链不应当是能被猜出来原意的
拓展需求
- 分析 比如对一个短链来说，重定向发生了多少次
- 我们的服务应当是Restful API的形式，方便其他服务访问。
资源占用和限制
整个系统是读频繁系统。我们假定读：写需求比例为100：1.
并发估计
假定我们每月有5亿URL短链转化需求，那么根据读写需求比例，我们可以知道每月会有500亿短链重定向需求。那么QPS（query per second）就是200URLs/s。而重定向需求是20000次/秒。
储存需求
对于一个五年周期，由于我们每月有5亿URL短链转化需求，所以5年有300亿累计需求。假定每条记录需要500字节存储，我们就需要15TB来储存这些数据。
带宽估计
对于写请求，因为我们估计每秒有200个URL短链转化需求，每条500字节，所以写入带宽需要在100KB/s左右。对于读请求来说，则是10MB/s左右。
内存估计
如果我们想储存一些被访问次数较多的“热点数据”，我们需要多少内存？按照2-8定律，我们会缓存20%的热点短链接。因为我们每秒重定向20000次，我们一天会有17亿次请求。所以乘以20%再乘以500字节，所需要的储存空间是170GB.值得一提的是由于有很多重复请求，最后我们用不到170GB.
最终估计
因此，我们知道这个服务需要：
- 新短链接请求：200/s
- URL重定向：20000/s
- 写带宽：100KB/s
- 读带宽：10MB/s
- 5年所需储存空间：15TB
- 内存：170GB
系统API
这时候，我们就能设计一个REST api了。
createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)
参数
api_dev_key(string): 开发者key,主要是方便记录用户的使用次数，计算配额。
original_url(string): 需要缩短的url
custom_alias(string): URL定制变量（可选）
user_name(string: 用户名（可选）
expire_date(string): 短链接的过期时间
返回值(string)
成功返回短链接地址，否则返回错误代码。
deleteURL(api_dev_key, url_key)
参数
api_dev_key(string): 开发者key,主要是方便记录用户的使用次数，计算配额。
url_key(string) 需要修改的短链接。
怎样避免API滥用？
恶意用户会将我们的所有URL全部耗尽，所以我们需要通过api_dev_key限制用户。每个key只能访问特定次数的服务，同时在一个时间段内，只能进行有限的重定向（避免服务过载）。
数据库设计
通过之前的研究我们能发现：
- 我们需要储存上10亿的数据
- 每个数据单元都很小（不足1K）
- 除了哪个用户创造了这个短链接，在表之前没有其他的关系（1对多，多对多）
- 我们的服务是读频繁服务
表设计
URL表
| 列名 | 数据类型 | 备注 |
|---|---|---|
| HashURL | varchar(16) | 主键 |
| OriginalURL | varchar(512) | 非空 |
| CreationDate | datetime | 非空 |
| ExpirationDate | datetime | 非空 |
| UserId | int | 外键 |
User表
| 列名 | 数据类型 | 备注 |
|---|---|---|
| UserId | int | 主键 |
| Name | varchar(20) | |
| varchar(32) | ||
| CreationDate | datetime | 非空 |
| LastLogin | datetime | 非空 |